package com.navinfo.tripanalysis.offline.util;


import lombok.Data;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 离群点分析
 *
 * @author hmc
 * 算法：基于密度的局部离群点检测（lof算法）
 * 输入：样本集合D，正整数K（用于计算第K距离）
 * 输出：各样本点的局部离群点因子
 * 过程：
 *  1）计算每个对象与其他对象的欧几里得距离
 *  2）对欧几里得距离进行排序，计算第k距离以及第K领域
 *  3）计算每个对象的可达密度
 *  4）计算每个对象的局部离群点因子
 *  5）对每个点的局部离群点因子进行排序，输出。
 **/
@Data
public class OutlierNodeDetect {
    private static double Percent_K = 0.2;//样本分组数量：K=

    // 1.找到给定点与其他点的欧几里得距离
    // 2.对欧几里得距离进行排序，找到前5位的点，并同时记下k距离
    // 3.计算每个点的可达密度
    // 4.计算每个点的局部离群点因子
    // 5.对每个点的局部离群点因子进行排序，输出。
    public static List<DataNode> getOutlierNode(List<DataNode> allNodes) {

        List<DataNode> kdAndKnList = getKDAndKN(allNodes);
        calReachDis(kdAndKnList);
        calReachDensity(kdAndKnList);
        calLof(kdAndKnList);
        //降序排序
        //Collections.sort(kdAndKnList, new LofComparator());

        return kdAndKnList;
    }

    /**
     * 计算每个点的局部离群点因子
     * @param kdAndKnList
     */
    private static void calLof(List<DataNode> kdAndKnList) {
        int INT_K = (int)(Percent_K*kdAndKnList.size());
        for (DataNode node : kdAndKnList) {
            List<DataNode> tempNodes = node.getkNeighbor();
            double sum = 0.0;
            for (DataNode tempNode : tempNodes) {
                double rd = getRD(tempNode.getNodeName(), kdAndKnList);
                sum = (node.getReachDensity() == 0.0 ? 0.0
                        : new BigDecimal(rd).divide(new BigDecimal(node.getReachDensity()),4,BigDecimal.ROUND_DOWN).doubleValue()) + sum;
            }
            sum = new BigDecimal(sum).divide(new BigDecimal(INT_K),4,BigDecimal.ROUND_DOWN).doubleValue();
            node.setLof(sum);
        }
    }

    /**
     * 计算每个点的可达密度
     * @param kdAndKnList
     */
    private static void calReachDensity(List<DataNode> kdAndKnList) {
        for (DataNode node : kdAndKnList) {
            List<DataNode> tempNodes = node.getkNeighbor();
            double sum = 0.0;
            double rd = 0.0;
            int INT_K = (int)(Percent_K*kdAndKnList.size());
            for (DataNode tempNode : tempNodes) {
                sum = tempNode.getReachDis() + sum;
            }
            //平均可达距离的倒数
            rd = sum == 0.0 ? 0.0:new BigDecimal(INT_K).divide(new BigDecimal(sum),4,BigDecimal.ROUND_DOWN).doubleValue();

            node.setReachDensity(rd);
        }
    }

    /**
     * 计算每个点的可达距离,reachdis(p,o)=max{ k-distance(o),d(p,o)}
     * @param kdAndKnList
     */
    private static void calReachDis(List<DataNode> kdAndKnList) {
        for (DataNode node : kdAndKnList) {
            List<DataNode> tempNodes = node.getkNeighbor();
            for (DataNode tempNode : tempNodes) {
                //获取tempNode点的k-距离
                double kDis = getKDis(tempNode.getNodeName(), kdAndKnList);
                //reachdis(p,o)=max{ k-distance(o),d(p,o)}
                if (kDis < tempNode.getDistance()) {
                    tempNode.setReachDis(tempNode.getDistance());
                } else {
                    tempNode.setReachDis(kDis);
                }
            }
        }
    }

    /**
     * 获取某个点的k-距离（kDistance）
     * @param nodeName
     * @param nodeList
     * @return
     */
    private static double getKDis(int nodeName, List<DataNode> nodeList) {
        double kDis = 0;
        for (DataNode node : nodeList) {
            if (nodeName == node.getNodeName()) {
                kDis = node.getkDistance();
                break;
            }
        }
        return kDis;

    }

    /**
     * 获取某个点的可达距离
     * @param nodeName
     * @param nodeList
     * @return
     */
    private static double getRD(int nodeName, List<DataNode> nodeList) {
        double kDis = 0;
        for (DataNode node : nodeList) {
            if (nodeName == node.getNodeName()) {
                kDis = node.getReachDensity();
                break;
            }
        }
        return kDis;

    }

    /**
     * 计算给定点NodeA与其他点NodeB的欧几里得距离（distance）,并找到NodeA点的前5位NodeB，然后记录到NodeA的k-领域（kNeighbor）变量。
     * 同时找到NodeA的k距离，然后记录到NodeA的k-距离（kDistance）变量中。
     * 处理步骤如下：
     * 1,计算给定点NodeA与其他点NodeB的欧几里得距离，并记录在NodeB点的distance变量中。
     * 2,对所有NodeB点中的distance进行升序排序。
     * 3,找到NodeB点的前5位的欧几里得距离点，并记录到到NodeA的kNeighbor变量中。
     * 4,找到NodeB点的第5位距离，并记录到NodeA点的kDistance变量中。
     * @param allNodes
     * @return List<Node>
     */
    private static List<DataNode> getKDAndKN(List<DataNode> allNodes) {
        List<DataNode> kdAndKnList = new ArrayList<DataNode>();
        for (int i = 0; i < allNodes.size(); i++) {
            List<DataNode> tempNodeList = new ArrayList<DataNode>();
            DataNode nodeA = new DataNode(allNodes.get(i).getNodeName(), allNodes
                    .get(i).getDimensioin(),allNodes.get(i).getPointNum());
            //1,找到给定点NodeA与其他点NodeB的欧几里得距离，并记录在NodeB点的distance变量中。
            for (int j = 0; j < allNodes.size(); j++) {
                DataNode nodeB = new DataNode(allNodes.get(j).getNodeName(), allNodes
                        .get(j).getDimensioin());
                //计算NodeA与NodeB的欧几里得距离(distance)
                double tempDis = getDis(nodeA, nodeB);
                nodeB.setDistance(tempDis);
                tempNodeList.add(nodeB);
            }

            //2,对所有NodeB点中的欧几里得距离（distance）进行升序排序。
            Collections.sort(tempNodeList, new DistComparator());
            int INT_K = (int)(Percent_K*allNodes.size());
            for (int k = 1; k < INT_K; k++) {
                //3,找到NodeB点的前5位的欧几里得距离点，并记录到到NodeA的kNeighbor变量中。
                nodeA.getkNeighbor().add(tempNodeList.get(k));
                if (k == INT_K - 1) {
                    //4,找到NodeB点的第5位距离，并记录到NodeA点的kDistance变量中。
                    nodeA.setkDistance(tempNodeList.get(k).getDistance());
                }
            }
            kdAndKnList.add(nodeA);
        }

        return kdAndKnList;
    }

    /**
     * 计算给定点A与其他点B之间的欧几里得距离。
     * 欧氏距离的公式：
     * d=sqrt( ∑(xi1-xi2)^2 ) 这里i=1,2..n
     * xi1表示第一个点的第i维坐标,xi2表示第二个点的第i维坐标
     * n维欧氏空间是一个点集,它的每个点可以表示为(x(1),x(2),...x(n)),
     * 其中x(i)(i=1,2...n)是实数,称为x的第i个坐标,两个点x和y=(y(1),y(2)...y(n))之间的距离d(x,y)定义为上面的公式.
     * @param A
     * @param B
     * @return
     */
    private static double getDis(DataNode A, DataNode B) {
        double dis = 0.0;
        double[] dimA = A.getDimensioin();
        double[] dimB = B.getDimensioin();
        if (dimA.length == dimB.length) {
            for (int i = 0; i < dimA.length; i++) {
                double temp = Math.pow(dimA[i] - dimB[i], 2);
                dis = dis + temp;
            }
            dis = Math.pow(dis, 0.5);
        }
        return dis;
    }

    /**
     * 升序排序
     * @author zouzhongfan
     *
     */
    static class DistComparator implements Comparator<DataNode> {
        public int compare(DataNode A, DataNode B) {
            //return A.getDistance() - B.getDistance() < 0 ? -1 : 1;
            if((A.getDistance()-B.getDistance())<0)
                return -1;
            else if((A.getDistance()-B.getDistance())>0)
                return 1;
            else return 0;
        }
    }

    /**
     * 降序排序
     * @author zouzhongfan
     *
     */
    class LofComparator implements Comparator<DataNode> {
        public int compare(DataNode A, DataNode B) {
            //return A.getLof() - B.getLof() < 0 ? 1 : -1;
            if((A.getLof()-B.getLof())<0)
                return 1;
            else if((A.getLof()-B.getLof())>0)
                return -1;
            else return 0;
        }
    }

//    public static void main(String[] args) {
//
//        java.text.DecimalFormat   df   =new   java.text.DecimalFormat("#.####");
//
//        ArrayList<DataNode> dpoints = new ArrayList<DataNode>();

        /**
        double[] a = { 2, 3 };
        double[] b = { 2, 4 };
        double[] c = { 1, 4 };
        double[] d = { 1, 3 };
        double[] e = { 2, 2 };
        double[] f = { 3, 2 };

        double[] g = { 8, 7 };
        double[] h = { 8, 6 };
        double[] i = { 7, 7 };
        double[] j = { 7, 6 };
        double[] k = { 8, 5 };

        double[] l = { 100, 2 };// 孤立点

        double[] m = { 8, 20 };
        double[] n = { 8, 19 };
        double[] o = { 7, 18 };
        double[] p = { 7, 17 };
        double[] q = { 101, 21 };

        dpoints.add(new DataNode("a", a));
        dpoints.add(new DataNode("b", b));
        dpoints.add(new DataNode("c", c));
        dpoints.add(new DataNode("d", d));
        dpoints.add(new DataNode("e", e));
        dpoints.add(new DataNode("f", f));

        dpoints.add(new DataNode("g", g));
        dpoints.add(new DataNode("h", h));
        dpoints.add(new DataNode("i", i));
        dpoints.add(new DataNode("j", j));
        dpoints.add(new DataNode("k", k));

        dpoints.add(new DataNode("l", l));

        dpoints.add(new DataNode("m", m));
        dpoints.add(new DataNode("n", n));
        dpoints.add(new DataNode("o", o));
        dpoints.add(new DataNode("p", p));
        dpoints.add(new DataNode("q", q));

         **/

//        double[] a1={108362254,39429024};
//        double[] a2={108362085,39428912};
//        double[] a3={108361917,39428798};
//        double[] a4={108361748,39428685};
//        double[] a5={108361579,39428571};
//        double[] a6={108361409,39428458};
//        double[] a7={108361238,39428344};
//        double[] a8={108361068,39428230};
//        double[] a9={108360898,39428115};
//        double[] a10={108360727,39428001};
//        double[] a1={108362254,39429024};
//        double[] a2={108362254,39429024};
//        double[] a3={108362254,39429024};
//        double[] a4={108362254,39429024};
//        double[] a5={108362254,39429024};
//        double[] a6={108362254,39429024};
//        double[] a7={108362254,39429024};
//        double[] a8={108362254,39429024};
//        double[] a9={108362254,39429024};
//        double[] a10={108362254,39429024};
//
//        double[] a11={108357187,39425626};
//        double[] a12={108357021,39425516};
//        double[] a13={108356856,39425406};
//        double[] a14={108356691,39425295};
//        double[] a15={108356527,39425185};
//        double[] a16={108356362,39425075};
//        double[] a17={108356198,39424964};
//        double[] a18={108356032,39424854};
//        double[] a19={108355869,39424744};
//        double[] a20={108355704,39424633};
//        double[] a21={108352336,39422377};
//        double[] a22={108352176,39422269};
//        double[] a23={108352013,39422161};
//        double[] a24={108351853,39422052};
//        double[] a25={108351692,39421943};
//        double[] a26={108351529,39421835};
//        double[] a27={108351369,39421726};
//        double[] a28={108351207,39421617};
//        double[] a29={108351046,39421509};
//        double[] a30={108350885,39421400};
//        double[] a31={108349099,39420203};
//        double[] a32={108348936,39420095};
//        double[] a33={108348775,39419985};
//        double[] a34={108348613,39419877};
//        double[] a35={108348450,39419770};
//        double[] a36={108348290,39419661};
//        double[] a37={108348129,39419554};
//        double[] a38={108347968,39419446};
//        double[] a39={108347806,39419338};
//        double[] a40={108347643,39419232};
//        double[] a41={108347483,39419123};
//        double[] a42={108347323,39419016};
//        double[] a43={108347162,39418907};
//        double[] a44={108347002,39418799};
//        double[] a45={108346841,39418691};
//        double[] a46={108346680,39418583};
//        double[] a47={108346518,39418476};
//        double[] a48={108346357,39418367};
//        double[] a49={108346194,39418260};
//        double[] a50={109356032,39418152};
//        double[] a51={109355869,39418043};
//        double[] a52={109355706,39417933};
//        double[] a53={109355543,39417824};
//        double[] a54={109355378,39417712};
//        double[] a55={109355215,39417602};
//        double[] a56={109355051,39417489};
//        double[] a57={109354887,39417377};
//        double[] a58={109354722,39417266};
//        double[] a59={109354558,39417151};
//        double[] a60={108344393,39417038};
//        double[] a61={108344229,39416923};
//        double[] a62={108344065,39416807};
//        double[] a63={108343900,39416690};
//        double[] a64={108343736,39416572};
//        double[] a65={108343573,39416454};
//        double[] a66={108343409,39416336};
//        double[] a67={108343245,39416216};
//        double[] a68={108343082,39416095};
//        double[] a69={108342916,39415975};
//        double[] a70={108342752,39415853};
//        double[] a71={108340963,39414469};
//        double[] a72={108340804,39414340};
//        double[] a73={108340646,39414212};
//        double[] a74={108340491,39414085};
//        double[] a75={108340335,39413957};
//        double[] a76={108340183,39413831};
//        double[] a77={108340030,39413706};
//        double[] a78={108339882,39413580};
//        double[] a79={108339734,39413455};
//        double[] a80={108339588,39413331};
//        double[] a81={108339444,39413209};
//        double[] a82={108339303,39413087};
//        double[] a83={108339162,39412965};
//        double[] a84={108339022,39412844};
//        double[] a85={108338885,39412723};
//        double[] a86={108338746,39412603};
//        double[] a87={108338609,39412482};
//        double[] a88={108338472,39412360};
//        double[] a89={108338336,39412238};
//        double[] a90={108338201,39412116};
//        double[] a91={108338066,39411992};
//        double[] a92={108337930,39411871};
//        double[] a93={108337795,39411745};
//        double[] a94={108337660,39411620};
//        double[] a95={108337524,39411495};
//        double[] a96={108337388,39411366};
//        double[] a97={108337253,39411239};
//        double[] a98={108337115,39411110};
//        double[] a99={108336978,39410980};
//        double[] a100={108336842,39410849};
//
//        dpoints.add(new DataNode("a1",a1));
//        dpoints.add(new DataNode("a2",a2));
//        dpoints.add(new DataNode("a3",a3));
//        dpoints.add(new DataNode("a4",a4));
//        dpoints.add(new DataNode("a5",a5));
//        dpoints.add(new DataNode("a6",a6));
//        dpoints.add(new DataNode("a7",a7));
//        dpoints.add(new DataNode("a8",a8));
//        dpoints.add(new DataNode("a9",a9));
//        dpoints.add(new DataNode("a10",a10));
//        dpoints.add(new DataNode("a11",a11));
//        dpoints.add(new DataNode("a12",a12));
//        dpoints.add(new DataNode("a13",a13));
//        dpoints.add(new DataNode("a14",a14));
//        dpoints.add(new DataNode("a15",a15));
//        dpoints.add(new DataNode("a16",a16));
//        dpoints.add(new DataNode("a17",a17));
//        dpoints.add(new DataNode("a18",a18));
//        dpoints.add(new DataNode("a19",a19));
//        dpoints.add(new DataNode("a20",a20));
//        dpoints.add(new DataNode("a21",a21));
//        dpoints.add(new DataNode("a22",a22));
//        dpoints.add(new DataNode("a23",a23));
//        dpoints.add(new DataNode("a24",a24));
//        dpoints.add(new DataNode("a25",a25));
//        dpoints.add(new DataNode("a26",a26));
//        dpoints.add(new DataNode("a27",a27));
//        dpoints.add(new DataNode("a28",a28));
//        dpoints.add(new DataNode("a29",a29));
//        dpoints.add(new DataNode("a30",a30));
//        dpoints.add(new DataNode("a31",a31));
//        dpoints.add(new DataNode("a32",a32));
//        dpoints.add(new DataNode("a33",a33));
//        dpoints.add(new DataNode("a34",a34));
//        dpoints.add(new DataNode("a35",a35));
//        dpoints.add(new DataNode("a36",a36));
//        dpoints.add(new DataNode("a37",a37));
//        dpoints.add(new DataNode("a38",a38));
//        dpoints.add(new DataNode("a39",a39));
//        dpoints.add(new DataNode("a40",a40));
//        dpoints.add(new DataNode("a41",a41));
//        dpoints.add(new DataNode("a42",a42));
//        dpoints.add(new DataNode("a43",a43));
//        dpoints.add(new DataNode("a44",a44));
//        dpoints.add(new DataNode("a45",a45));
//        dpoints.add(new DataNode("a46",a46));
//        dpoints.add(new DataNode("a47",a47));
//        dpoints.add(new DataNode("a48",a48));
//        dpoints.add(new DataNode("a49",a49));
//        dpoints.add(new DataNode("a50",a50));
//        dpoints.add(new DataNode("a51",a51));
//        dpoints.add(new DataNode("a52",a52));
//        dpoints.add(new DataNode("a53",a53));
//        dpoints.add(new DataNode("a54",a54));
//        dpoints.add(new DataNode("a55",a55));
//        dpoints.add(new DataNode("a56",a56));
//        dpoints.add(new DataNode("a57",a57));
//        dpoints.add(new DataNode("a58",a58));
//        dpoints.add(new DataNode("a59",a59));
//        dpoints.add(new DataNode("a60",a60));
//        dpoints.add(new DataNode("a61",a61));
//        dpoints.add(new DataNode("a62",a62));
//        dpoints.add(new DataNode("a63",a63));
//        dpoints.add(new DataNode("a64",a64));
//        dpoints.add(new DataNode("a65",a65));
//        dpoints.add(new DataNode("a66",a66));
//        dpoints.add(new DataNode("a67",a67));
//        dpoints.add(new DataNode("a68",a68));
//        dpoints.add(new DataNode("a69",a69));
//        dpoints.add(new DataNode("a70",a70));
//        dpoints.add(new DataNode("a71",a71));
//        dpoints.add(new DataNode("a72",a72));
//        dpoints.add(new DataNode("a73",a73));
//        dpoints.add(new DataNode("a74",a74));
//        dpoints.add(new DataNode("a75",a75));
//        dpoints.add(new DataNode("a76",a76));
//        dpoints.add(new DataNode("a77",a77));
//        dpoints.add(new DataNode("a78",a78));
//        dpoints.add(new DataNode("a79",a79));
//        dpoints.add(new DataNode("a80",a80));
//        dpoints.add(new DataNode("a81",a81));
//        dpoints.add(new DataNode("a82",a82));
//        dpoints.add(new DataNode("a83",a83));
//        dpoints.add(new DataNode("a84",a84));
//        dpoints.add(new DataNode("a85",a85));
//        dpoints.add(new DataNode("a86",a86));
//        dpoints.add(new DataNode("a87",a87));
//        dpoints.add(new DataNode("a88",a88));
//        dpoints.add(new DataNode("a89",a89));
//        dpoints.add(new DataNode("a90",a90));
//        dpoints.add(new DataNode("a91",a91));
//        dpoints.add(new DataNode("a92",a92));
//        dpoints.add(new DataNode("a93",a93));
//        dpoints.add(new DataNode("a94",a94));
//        dpoints.add(new DataNode("a95",a95));
//        dpoints.add(new DataNode("a96",a96));
//        dpoints.add(new DataNode("a97",a97));
//        dpoints.add(new DataNode("a98",a98));
//        dpoints.add(new DataNode("a99",a99));
//        dpoints.add(new DataNode("a100",a100));
//
//
//        OutlierNodeDetect lof = new OutlierNodeDetect();
//
//        List<DataNode> nodeList = lof.getOutlierNode(dpoints);
//
//        for (DataNode node : nodeList) {
//            System.out.println(node.getNodeName() + "  " + df.format(node.getLof()));
//        }
//
//    }

}
